Date: Tue, 10 Dec 1996 03:25:53 GMT
Server: NCSA/1.4.2
Content-type: text/html

<html>
<head>
<TITLE>The SkyBlue Constraint Solver and Its Applications</title>
</head>

<body>

<H2>The SkyBlue Constraint Solver and Its Applications</H2>

<p>

Author: Michael Sannella

<p>

To appear in Vijay Saraswat and Pascal van Hentenryck (eds),
<em>Proceedings of the 1993 Workshop on Principles and Practice of
Constraint Programming</em>, MIT Press, 1994.  

<P>
<hr>

<H3>Abstract</H3>

The SkyBlue constraint solver uses multi-way local propagation to
efficiently maintain constraints organized in a constraint hierarchy.  As
individual constraints are added and removed, SkyBlue executes
<em>method</em> procedures associated with each constraint to incrementally
resatisfy the constraints.  SkyBlue is a successor to the DeltaBlue
algorithm, which has two significant limitations: cycles of constraints are
prohibited, and constraint methods can only have a single output variable.
SkyBlue relaxes these restrictions, satisfying cycles of constraints by
calling external solvers and supporting multi-output methods.

<P>

This paper compares SkyBlue to other constraint solvers, describes the
SkyBlue algorithm and discusses several applications that have been built
using SkyBlue.  The SkyBlue algorithm description introduces several new
concepts including <em>method vines</em> (used to select which methods to
execute) and <em>walkbounds</em> (a generalization of DeltaBlue's
<em>walkabout strengths</em>).

<P>
<HR>
<P>

Click <!WA0><a href=
"ftp://cs.washington.edu/pub/constraints/papers/skyblue-ppcp-93.ps.Z">
here</a> to get the postscript file.

<P>

Return to <!WA1><a href="http://www.cs.washington.edu/research/projects/weird/www/index.html">Constraints home page</a>
